#pragma once
#include <vector>
using std::vector;

namespace my_priority_queue
{
    template <typename T>
    struct Less
    {
        bool operator() (const T& t1, const T& t2) const
        {
            return t1 < t2;
        }
    };

    // priority_queue 默认是大根堆，重写小于
    template <typename T, typename Container = vector<T>, typename Compare = Less<T>>
    class priority_queue
    {
        typedef priority_queue<T, Container, Compare> self;

    private:
        // 建堆操作
        // 自顶向下建堆
        void UpToDown(size_t parent)
        {
            size_t child = parent * 2 + 1;
            while (child < _pq.size())
            {
                // 如果右孩子不存在，则是左孩子
                // 如果右孩子存在，且其孩子的值小于左孩子则是左孩子
                child = child + 1 < _pq.size() && _cmp(_pq[child], _pq[child + 1]) ? child + 1 : child;
                // 如果孩子节点小 父亲节点大 则直接退出循环
                if (_cmp(_pq[child], _pq[parent]))
                    break;
                // 孩子节点大，父亲节点小 交换
                std::swap(_pq[child], _pq[parent]);
                parent = child;
                child = parent * 2 + 1;
            }
        }

        // 自底向上建堆
        void DownToUp(size_t child)
        {
            size_t parent = (child - 1) / 2;
            // 类型是无符号的
            while (child > 0 && child < _pq.size())
            {
                if (_cmp(_pq[child], _pq[parent]))
                    break;
                std::swap(_pq[child], _pq[parent]);
                child = parent;
                parent = (child - 1) / 2;
            }
        }

        void CreateHeap()
        {
            // 自顶向下建堆
            int first = (_pq.size() - 1 - 1) / 2;
            for (int i = first; i >= 0; i--)
            {
                UpToDown(i);
            }
            // 自下而上建堆
            //for(int i = _pq.size() - 1; i >= 0; i--)
            //{
            //    DownToUp(i);
            //}
        }

    public:
        // Compare()：这个匿名对象，根据模板参数来确定是什么类型的匿名对象
        // 如果外面没有传入值，则使用Less<T>作为类型，生成Less<T>的匿名对象
        priority_queue(const Compare& cmp = Compare(), const Container& con = Container())
            : _pq(con),
            _cmp(cmp)
        {
        }

        template <class InputIterator>
        priority_queue(InputIterator first, InputIterator last,
            const Compare& cmp = Compare(), const Container& con = Container())
            : _pq(con),
            _cmp(cmp)
        {
            Container tmp(first, last);
            _pq.swap(tmp);
            CreateHeap();
        }

        void pop()
        {
            std::swap(_pq[0], _pq[_pq.size() - 1]);
            _pq.pop_back();
            UpToDown(0);
        }

        T& top()
        {
            return _pq[0];
        }

        void push(const T& val)
        {
            _pq.push_back(val);
            DownToUp(_pq.size() - 1);
        }
        size_t size()
        {
            return _pq.size();
        }

        void swap(self& pq)
        {
            _pq.swap(pq._pq);
        }
        bool empty()
        {
            return _pq.empty();
        }

    private:
        Container _pq;
        Compare _cmp;
    };
}